
import random

class Node(object):
    '''查找二叉树的节点.

    Attributes:
        key: 键，方便起见，这里用整数，实际情况中不一定是整数，字符串也许是更好的选择
        value: 值
        n：节点数,对应为 子树的节点数加本身的1
    '''
    def __init__(self, key:int, value:str, n:int):
        self.key = key
        self.value = value
        self.left:Node = None
        self.right:Node = None
        self.n:int = n       

class BST(object):
    def __init__(self):
        self.__root:Node = None

    def size(self) -> int:
        return self.__size(self.__root)

    def get(self, key:int) -> str:
        return self.__get(self.__root, key)

    def __get(self, node:Node, key:int) -> str:
        if node == None:
            return None
        if key == node.key:
            return node.value
        elif key > node.key:
            return self.__get(node.right, key)
        else:
            return self.__get(node.left, key)

    def put(self, key:int, value:str):
        if self.__root == None:
            self.__root = Node(key, value, 1)
        else:
            self.__put(self.__root, key, value)

    
    def __put(self, node:Node, key:int, value:str):
        if key == node.key:
            node.value = value
        else:
            if key < node.key:
                if node.left == None:
                    node.left = Node(key, value, 1)
                else:
                    self.__put(node.left, key, value)
            else:
                if node.right == None:
                    node.right = Node(key, value, 1)
                else:
                    self.__put(node.right, key ,value)
            node.n = self.__size(node)


    def __size(self, node:Node) -> int:
        if node == None:
            return 0
        return self.__size(node.left) + self.__size(node.right) + 1  

if __name__ == "__main__":
    bst = BST()

    l = [random.randint(1,20) for _ in range(20)]
    print(l)

    for i in l:
        bst.put(i, i)
    
    for i in l:
        print(bst.get(i))
    
    print("size:", bst.size())